package Hot100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author zhangmin
 * @create 2022-01-07 15:54
 */
public class removeInvalidParentheses301 {

    /**
     * 301. 删除无效的括号
     * 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。返回所有可能的结果。答案可以按 任意顺序 返回。
     * dfs，使用set去重：遇到左括号+1，遇到右括号-1，则合法的字符串需要
     *     对于一个合法的方案而言，必然有最终得分为 0；
     *     搜索过程中不会出现得分值为 负数 的情况
     * 可以首先计算出需要删除的字符个数，得到最终最长len的长度，用来剪枝
     * */
    Set<String> set=new HashSet<>();
    int max,len;
    String str;
    //index标识遍历到了str中的哪一位，path记录当前遍历的路径，l，r表示左右括号需要删除的个数
    void dfs(int index,String path,int l,int r,int count){
        if (l<0||r<0||count<0||count>max) return;
        if (l==0&&r==0){
            //左括号和右括号都用完了
            if (path.length()==len) set.add(path);
        }
        if (index==str.length()) return;
        char c = str.charAt(index);
        if (c=='('){
            //选择：加入路径或者不加入路径
            dfs(index+1,path+String.valueOf(c),l,r,count+1);
            //选择不加入，则相当于删除一个括号
            dfs(index+1,path,l-1,r,count);
        }else if (c==')'){
            dfs(index+1,path+String.valueOf(c),l,r,count-1);
            dfs(index+1,path,l,r-1,count);
        }else {
            //遇到字符，直接加入
            dfs(index+1,path+String.valueOf(c),l,r,count);
        }
    }
    public List<String> removeInvalidParentheses(String s) {
        str=s;
        //l,r记录需要删除的左右括号的个数，c1，c2记录左右括号出现的次数，用来计算最终的合法长度
        int l=0,r=0,c1=0,c2=0;
        for (char c:s.toCharArray()) {
            if (c=='('){
                l++;c1++;
            }else if (c==')'){
                c2++;
                if (l!=0) l--;
                else r++;
            }
        }
        len=s.length()-l-r;
        max=Math.min(c1,c2);
        dfs(0,"",l,r,0);
        return new ArrayList<>(set);
    }

}
